package algorithm.variousAlgorithm;

/**
 * @ClassName: FindKthNumber
 * @Description 440. 字典序的第K小数字
 * 给定整数 n 和 k，返回  [1, n] 中字典序第 k 小的数字。
 * @Author skywingking
 * @Date 2022/3/23 9:24 下午
 **/
public class FindKthNumber {
    public int findKthNumber(int n, int k) {
        int curr = 1;
        k--;
        while (k > 0) {
            int steps = getSteps(curr, n);
            if (steps <= k) {
                k -= steps;
                curr++;
            } else {
                curr = curr * 10;
                k--;
            }
        }
        return curr;
    }

    public int getSteps(int curr, long n){
        int steps = 0;
        long first = curr;
        long last = curr;
        while(first <= n){
            steps += Math.min(last,n) - first + 1;
            first = first * 10;
            last = last * 10 + 9;
        }
        return steps;
    }
}